.SS(Rapprochement: In retrospect,,P90:)

As with the  review section of the previous chapter, this section
is a mixture of the practical and the theoretical.  That is a healthy
attitude to cultivate when discussing programming languages.
For example, in the first section of this chapter we claimed that
a theoretically expected relationship between call-by-name and
call-by-value breaks down in the presence of side-effects.
The idea of side-effects is a decidedly  practical one, based on the 
"practical" notion
of a "variable" as a "box which contains a value", rather than the
mathematical notion of a "variable" as a  description for an
anonymous, but fixed, element of a domain.

.BEGIN GROUP;TURN OFF "←";
.P278:
Consider the following expression:
.SELECT 3; TABIT3(10,17,20);

prog [[ ]\y ← 0;
\λ[[x] prog[[ ]
\\loop\[eq[y;0] → go[loop]]]
\ [y ← 1]]]

.FILL;SELECT 1;
If this expression is evaluated using call-by-value, we bind %3y%1 to %30%1,
and evaluate the anonymous λ-expression. That entails evaluation of
%3y#←#1%1, %2before%1  entering the %3prog%1. The computation of the
%3prog%1#body terminates, returning %3NIL%1.
Call-by-name evaluation  would not evaluate %3y#←#1%1  and the computation
would not terminate.
.END
The issue of side-effects highlights an important distinction between
"variables" in the mathematical sense and "variables" in the programming sense.
In mathematics, we use the term, variable, to designate a fixed, but anonymous,
object: "let %3x%1 be a real number#...". In programming languages,
an object is "variable" as opposed to a "constant", meaning that the quantity
associated with the object may vary. Thus the idea of "box which contains a value"
arises again. The manipulation of variables in languages leads to further
distinctions. 

Applicative languages, modelled after the %9λ%1-calculus,
simulate the reduction rules by associating an environment or symbol table
with an expression. What is being simulated is a "copy#rule" which
says that the  reduction is to be done by making a copy of the expression,  
substituting the actual parameters into the copy wherever one of the %9λ%1-variables
appeared in the original expression. The effect of the symbol table is to
%2share%1 a common instance of the actual parameter. The idea of sharing
becomes  central when we discuss assignments and the behavior of side-effects.
If %2copies%1 of values are made, there issue of side-effects vanishes.
Important distinctions arise
when we are able  both to %2share%1  values
to destructively %2change%1 values. This combination  of properties is present
in the general assignment  statement.  Because of the close relationship
between assignment and LISP's λ-binding, λ-binding is sometimes
called a "pushdown" assignment (⊗↑[New#61]↑), as compared with a "destructive"
assignment.
The adjective, "pushdown", refers to the λ-binding's ability to save the
prior binding of a λ-variable in such a way that it may be restored
after the computation is completed.



We had enriched the LISP subset to allow such constructs as 
iteration and assignment; therefore, we  wished to provide an evaluator which
adequately reflected the implementation, or pragmatics,
of these facilities. We could have  modelled then directly in the initial
LISP subset, but the representation would not  convey the intended
implementation. As a result, we developed an interpreter which can
directly model  the effect of assignment statements, %3return%1 statements,
and non-local %3go%1 statements; these are some of the most troublesome
areas to  reflect in an applicative model.

The result of our investigations was the evaluator %3peval%1. This evaluator
plays the role of the evaluators of the previous chapter; it
expresses the implementation of the enriched subset of LISP; it 
is self-explanatory in the sense that  any construct which %3peval%1
uses has a data structure representation which is recognizable by %3peval%1.
That is, %3peval%1 can interpreted expressions involving representations
of %3peval%1.

The process of developing %3peval%1  exposed the control structure of LISP
just as the development of %3eval%1 in {yonsec(P113)} exposed
the access structure. {yonsec(P113)} developed data structure models for
access environments; this was necessary since the implementation of %3function%1
demanded it. Traditional LISP does not allow such generality in the area of
control structure.
The appearance of non-local %3go%1s and %3return%1s requires
control behavior analogous to functional arguments, but control regimes
analogous to functional %2values%1 do not appear. More recent demands
from LISP users have  prompted development of generalized
control structures in LISP-like languages (⊗↑[Hew#72]↑, ⊗↑[Pre#72]↑, ⊗↑[Pre#76a]↑,
⊗↑[Bob#73a]↑,⊗↑[Con#73]↑). Now that we have developed the data structure
representation for control, we could  extend LISP to  allow
 manipulation of control structures. We resist that temptation,
leaving such experimentation to the reader.

As we have just seen there are 
alternatives to some of the LISP-techniques and there are some things
which, in retrospect, LISP could have done better.
There are some
conceptual difficulties with LISP evaluation.
We have seen some  computational schemes which
will give values when LISP's call-by-value does not terminate.
Whether these schemes are better is a debatable point.
Programmers tend to think "call-by-value", but  it is not clear 
whether that is habit,
training, or a fundamental point of view towards computation.


The prcatical and the theoretical aspects of programming languages have
several common interests.
As we have seen, the notion of "function" 
in mathematics is different from the notion
of "LISP function". The former is a set-theoretic notion, the latter is
an algorithmic notion. With the introduction of iteration, a further
discrimination is useful. This requires a discussion of "recursive".
A useful classification appears in ⊗↑[Hew#76]↑.

.BEGIN INDENT 0,3; GROUP;
%21.%1 "Recursive" in the sense of recursive function theory (⊗↑[Rog#69]↑)
meaning that there is an algorithm which specifies the function.
This involves a precise study of the concepts of algorithm and computability.

%22.%1 "Recursive" in the sense of self-referential. The definition
of an algorithm  makes reference to the algorithm itself.
The idea of "self-reference" needs to be  handled carefully.
The definition may involve  mutual recursion: %3f%1 calls %3g%1, and %3g%1
calls %3f%1. Also, we saw on {yon(P99)} that  a function may be
dynamically self-referentially, while the static text is not.

%23.%1 Finally, "recursive" is used  meaning "non-iterative".
This is the usual interpretation imposed in programming languages.
This sense implies some assumptions about the   evaluation implementation.
Basically, it is to mean that  a recursive evaluation will require
more bookkeeping than the iterative evaluation. 
A problem on {yon(P281)} asked for an iterative evaluation of
%3fact[2]%1; fewer environments were created there than we required
for the evaluation of the "recursive" (in the sense of %22%1) version.
This third use of the word "recursive" is the least well defined and understood.
It is frequently believed that "recursive" is the sense of %22%1
implies  the third "recursive". The third sense is more a property of the
implementation of the evaluation scheme than a property of the algorithm.
Techniques are know for evaluating several classes of "recursive"
algorithms using iterative storage requirements; ⊗↑[Hew#76]↑,
⊗↑[Sus#76]↑, ⊗↑[Gre#76a]↑.
.END

Since the ideas involved in "recursive" are so important to LISP
and programming languages in general, we want to explore the ideas
further.  We will be most concerned with "recursive" in sense %22%1;
we want to understand what is involved in giving a recursive definition.
We now have three ways to define functions: the %3label%1 operator,
the "<="#operator, and the assignment statement. We need to understand
the differences between these operations.

.BEGIN GROUP;TURN OFF "←";
To begin with, we were able to give
counterexamples to interpreting:
.BEGIN CENTER;turn off "←";

%3f <= λ[[x] %9x%1] as %3f ← λ[[x] %9x%3].
.END
The discussion of binding and environments made %3f#←#function[λ[[x]#%9x%3]]%1
a more likely candidate; however this interpretation is also not adequate.
.END

.GROUP

.BEGIN CENTERit;

We attempt to implement ←%3fact <= λ[[x][x=0 → 1; %et%* → *[x;fact[x-1]]]]%1 as:
.END

.BEGIN CENTER;SELECT 3;TURN OFF "←";

fact ← function[λ[[x] ... fact[x-1] ...]
.END
.APART

.BEGIN TABIT3(30,34,38);GROUP;turn off "←";
Consider an initial environment with %3fact%1 defined:

\\E%4i%*
\E%4c%*\|\E%4a%*
\___________
\%3fact%*\|%3λ[[x] ...fact[x-1]] : %1E%4i%*

.apart;
.GROUP;
.BEGIN FILL;
.P276:
We will demonstrate the inadequacy of two natural interpretations of function
values: direct assignment of value, and assignment of %3funarg%1.
We execute %3foo ← fact%* and %3baz ← function[fact]%1, giving:
.END

\\E%4i%*
\E%4c%*\|\E%4a%*
\___________
\%3fact%*\|%3λ[[x] ...fact[x-1]] : %1E%4i%*
\%3foo%*\|%3λ[[x] ...fact[x-1]] : %1E%4i%*
\%3baz%*\|%3fact : %1E%4i%*
.APART